// @algorithm @lc id=739 lang=cpp 
// @title daily-temperatures

// @test([73,74,75,71,69,72,76,73])=[1,1,4,2,1,1,0,0]
// @test([30,40,50,60])=[1,1,1,0]
// @test([30,60,90])=[1,1,0]
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        auto & t = temperatures;
        vector<int> ans(t.size(), 0);
        for(int i=0; i<t.size(); i++){
            while(!stk.empty() && t[stk.top()]<t[i]){
                ans[stk.top()] = i-stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};